/**
 * 给定数组A，Q个操作，询问有2种：
 * 1. 单点修改
 * 2. [L, R], 在[L, R]中选择一段(长度至少是2)，记作[i, j]，再把[i, j]分成两段
 *    要求前一段减去后一段之差最大
 *
 * 与G一样，但是有负数。于是不能基于贪心的思想。
 * 考虑使用线段树直接维护。
 * 
 * 为了快速的得到整段的答案，需要维护多个信息：
 * 区间和，最小前缀和，最大后缀和，左起答案，右起答案，双端答案，答案
 * 
 * 其中双端答案是指恰好取整个区间能够拿到的答案，
 * 而答案是指在整个区间中任取子段能够拿到的答案
 * 其中前三个比较好维护。考虑后面4个答案。
 * 其关键就在于在哪里开始变为减号。
 * 一共有3种可能，恰好发生在连接处，在左半边就开始减，在右半边才开始减
 * 
 * 左起答案 = max(
 *     左一半左起答案, 
 *     左一半双端答案 - 右一半最小前缀和, // 这是在左半边就开始减的
 *     左一半区间和 + 右一半左起答案, // 这是在右半边才开始减的
 *     左一半区间和和 - 右一半最小前缀和 // 这是恰好减在连接处的
 * )
 * 
 * 其余有关答案信息类似与此
 * 
 * 合并的时候既有和值又有最值、又有负数，所以专门写了一个null成员，以便query处合并的代码不用修改
 * 其实改写query就行了，不过没有超时就可行
 */
#include <bits/stdc++.h>
using namespace std;

template <typename T>
const T & mymax(const T & a, const T & b){
    return max(a, b);
}

template<typename T, typename ... Args>
const T & mymax(const T & t, const Args & ... args){
    return max(t, mymax(args ...));
}


struct SegTree{ // 线段树带延迟

using llt = long long;

int N;

struct value_type{
    llt sum;
    llt leftmin;
    llt rightmax;
    llt lans;
    llt rans;
    llt full;
    llt ans;
    int null;
    value_type():null(1){}
    value_type(llt x):sum(x),leftmin(x),rightmax(x),lans(-inf()),rans(-inf()),full(-inf()),ans(-inf()),null(0){}
};

vector<value_type> data; // 线段树

using lazy_type = llt;
vector<lazy_type> lazy; // 延迟标记

/// 从下往上计算信息，要变动
value_type _up_(const value_type & ls, const value_type & rs) {
    // assert(0);
    if(ls.null) return rs;
    if(rs.null) return ls;

    value_type ans;
    ans.null = 0;
    
    ans.sum = ls.sum + rs.sum;

    ans.leftmin = min(ls.leftmin, ls.sum + rs.leftmin);

    ans.rightmax = max(rs.rightmax, ls.rightmax + rs.sum);

    ans.lans = mymax(ls.lans, ls.sum + rs.lans, ls.sum - rs.leftmin, ls.full - rs.leftmin);

    ans.rans = mymax(rs.rans, ls.rightmax + rs.full, ls.rightmax - rs.sum, ls.rans - rs.sum);

    ans.full = mymax(ls.sum - rs.sum, ls.sum + rs.full, ls.full - rs.sum);

    ans.ans = mymax(ls.ans, rs.ans, ls.rightmax - rs.leftmin, ls.rans - rs.leftmin, ls.rightmax + rs.lans);

    return ans;
}

/// 从上往下计算信息，要变动
void _dn_(int t, int s, int e, const lazy_type & delta) {
    // assert(0);
    data[t] = {delta};
}

/// 初始化，清零，不用动
void init(int n) {
    data.assign((N = n) + 1 << 2, value_zero());
    lazy.assign(n + 1 << 2, lazy_zero());
}

/// 这个函数不用动
void modify(int a, int b, const lazy_type & delta){
    _modify(1, 1, N, a, b, delta);
}

/// 这个函数不用动
value_type query(int a, int b){
    return _query(1, 1, N, a, b);
}

/// 这个函数不用动
void build(int n) {
    _build(1, 1, n);
}

/// 几乎不用动
value_type _query(int t, int s, int e, int a, int b) {
    if(a <= s and e <= b) {
        return data[t];
    }
    _pushDown(t, s, e);
    int mid = (s + e) >> 1;
    value_type ans = value_zero(); // 如果求最值，这里不能用zero
    if(a <= mid) ans = _up_(ans, _query(lson(t), s, mid, a, b));
    if(mid < b) ans = _up_(ans, _query(rson(t), mid + 1, e, a, b));
    return ans;
}

/// 几乎不用动
void _modify(int t, int s, int e, int a, int b, const lazy_type & delta) {
    if(a <= s and e <= b) {
        _dn_(t, s, e, delta);
        return;
    }
    _pushDown(t, s, e);
    int mid = (s + e) >> 1;
    if(a <= mid) _modify(lson(t), s, mid, a, b, delta);
    if(mid < b) _modify(rson(t), mid + 1, e, a, b, delta);
    _pushUp(t);
    return;
}

/// 这个函数不用动
void _pushUp(int t) {
    data[t] = _up_(data[lson(t)], data[rson(t)]);
}

/// 这个函数几乎不用动
void _pushDown(int t, int s, int e) {
    if(lazy_zero() == lazy[t]) return;
    auto & lz = lazy[t];
    auto ls = lson(t), rs = rson(t);
    int mid = (s + e) >> 1;

    _dn_(ls, s, mid, lz);
    _dn_(rs, mid + 1, e, lz);

    lz = lazy_zero();
}


/// 几乎不用动
void _build(int t, int s, int e) {
    if(s == e) {
        int x; cin >> x;
        data[t] = value_type(x); // 注意提供value_type的初始化
        return; 
    }
    int mid = (s + e) >> 1;
    _build(lson(t), s, mid);
    _build(rson(t), mid + 1, e);
    _pushUp(t);
}

/// 辅助函数，视延迟的类型而变动
static const lazy_type & lazy_zero() {
    static const lazy_type LAZY0 = 0;
    return LAZY0; 
}

/// 辅助函数，视线段树信息类型而变动
static const value_type & value_zero() {
    static const value_type VALUE0;
    return VALUE0;
}

static const llt inf(){
    static const llt INF = 0x7F8F9FAFBFCFDFEF;
    return INF;
}

/// 这两个函数不用变动
static int lson(int x) {return x << 1;}
static int rson(int x) {return lson(x) | 1;}


};


using llt = long long;
using vi = vector<int>;
using pii = pair<int, int>;

SegTree St;

int N;
int Q;

void proc(){
    St.init(N);
    St.build(N);

    for(int c,x,y,q=1;q<=Q;++q){
        cin >> c >> x >> y;
        if(1 == c){
            St.modify(x, x, y);
        }else{
            auto ans = St.query(x, y);
            cout << ans.ans << "\n";
        }
    }
    return;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int nofkase = 1; 
    cin >> nofkase;
    while(nofkase--){
        cin >> N >> Q;
        proc();
    }
    return 0;
}